package tu.bianli;

import tu.juzheng.IGraph;

public class Tu_DFS {
    private static boolean[] visited;       //访问标志数组
    
    public static void DFSTraverse(IGraph G)throws Exception{       //对图G做深度优先遍历
        visited = new boolean[G.getVexNum()];                       
        for (int v = 0; v < G.getVexNum(); v++) {
            visited[v] = false;
        }
        for (int v = 0; v < G.getVexNum(); v++) {
            if(!visited[v])
                DFS(G, v);                                          //对尚未访问的的邻接顶点m递归调用DFS
        }
    }

    public static void DFS(IGraph G, int v)throws Exception{
        //从第v个顶点出发递归地深度优先遍历图G
        visited[v] = true;
        System.out.println(G.getVex(v).toString() + " ");
        for (int w = G.firstAdjVex(v); w >= 0 ; w = G.nextAdjVex(v, w)) {
            if(!visited[w]){                //对v的尚未访问的邻接顶点w递归调用DFS
                DFS(G, w);  
            }
        }
    }
}
